/*
AI 生成，我使用滑动窗口没有解题思路

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。


示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

*/

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        // 边界情况：如果s的长度小于p，直接返回空结果
        if (s.length() < p.length()) return result;

        // 创建字符计数数组，用于统计p中每个字符的出现次数
        int[] count = new int[26];
        for (char c : p.toCharArray()) {
            count[c - 'a']++;  // 初始化p的字符频率
        }

        // 初始化滑动窗口指针和变量
        int left = 0, right = 0;        // 滑动窗口的左右边界
        int pLen = p.length();          // 模式串p的长度
        int sLen = s.length();          // 字符串s的长度
        int need = pLen;                // 还需要匹配的字符总数（初始为p的长度）

        // 开始滑动窗口遍历
        while (right < sLen) {
            // 右指针处理：扩大窗口
            char rightChar = s.charAt(right);
            // 如果当前字符在p中存在（count值>0），说明匹配了一个有效字符
            if (count[rightChar - 'a'] > 0) {
                need--;  // 需要匹配的字符数减少
            }
            count[rightChar - 'a']--;  // 减少该字符的计数（无论是否在p中）
            right++;                   // 右指针右移

            // 检查是否找到异位词：当need为0时，说明窗口内字符与p完全匹配
            if (need == 0) {
                result.add(left);  // 记录当前窗口的起始位置
            }

            // 当窗口大小等于p的长度时，需要收缩窗口
            if (right - left == pLen) {
                char leftChar = s.charAt(left);
                // 如果移出的字符在p中（count值>=0），说明失去了一个有效字符
                if (count[leftChar - 'a'] >= 0) {
                    need++;  // 需要匹配的字符数增加
                }
                count[leftChar - 'a']++;  // 恢复该字符的计数
                left++;                   // 左指针右移，收缩窗口
            }
        }

        return result;
    }
}